package demo1;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    //子集 2
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        res.add(new LinkedList<>()); // 空集
        dfs(0, nums, new LinkedList<>());
        return res;
    }
    public void dfs(int idx, int[] nums, List<Integer> list) {
        if (idx >= nums.length) {
            return;
        }
        int end = idx; // 找到最后一个相同的元素
        for (; end < nums.length; end++) {
            if (nums[end] != nums[idx]) {
                break;
            }
        }
        // 选
        for (int i = idx; i < end; i++) {
            list.add(nums[i]);
            res.add(new LinkedList<>(list));
            dfs(end, nums, list);
        }
        for (int i = idx; i < end; i++) {
            list.remove(list.size() - 1);
        }
        // 不选
        dfs(end, nums, list);
    }

    //搜索旋转排序数组
    public int search(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n-1;
        while (left < right) {
            int mid = left+(right-left)/2;
            if(nums[mid]>nums[n-1]) left = mid+1;
            else right = mid;
        }
        if(target<=nums[n-1]){
            right = n-1;
            while(left<right){
                int mid = left+(right-left)/2;
                if(nums[mid]<target) left = mid+1;
                else right = mid;
            }
            if(nums[right] == target) return right;
            else return -1;
        }else{
            left = 0;
            right = right == 0?0:right-1;
            while(left<right){
                int mid = left+(right-left)/2;
                if(nums[mid]<target) left = mid+1;
                else right = mid;
            }
            if(nums[right] == target) return right;
            else return -1;
        }
    }
}
